package leetcode.code0990;

public class Solution1 {

	int[] p;

	public void init(int size) {
		p = new int[size];
		for (int i = 0; i < p.length; i++) {
			p[i] = i;
		}
	}

	public void union(int a, int b) {
		p[find(a)] = find(b);
	}

	public int find(int id) {
		if (p[id] != id) {
			p[id] = this.find(p[id]);
		}
		return p[id];
	}

	public boolean isSameSet(int a, int b) {
		return find(a) == find(b);
	}

	public boolean equationsPossible(String[] equations) {
		this.init(26);
		for (String equ : equations) {
			if (equ.charAt(1) == '=') {
				union(equ.charAt(0), equ.charAt(3));
			}
		}
		for (String equ : equations) {
			if (equ.charAt(1) == '!') {
				if (isSameSet(equ.charAt(0), equ.charAt(3))) {
					return false;
				}
			}
		}
		return true;
	}
}
